Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks. OSPF is a link-state routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables, is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use algorithms that calculate the shortest path to various routers (network nodes). The largest entity within the hierarchy is an autonomous system (AS), which is a collection of networks under a common administration that share a common routing strategy. OSPF is an intra-AS (interior gateway) routing protocol, although it is capable of receiving routes from and sending routes to other ASs. An AS can be divided into a number of areas, which are groups of contiguous networks and attached hosts. Routers with multiple interfaces can participate in multiple areas. These routers, which are called Area Border Routers, maintain separate topological databases for each area. A topological database is essentially an overall picture of networks in relationship to routers. The topological database contains the collection of LSAs received from all routers in the same area. Because routers within the same area share the same information, they have identical topological databases.
The Shortest Path First (SPF) routing algorithm is the basis for OSPF operations. When a router using the SPF algorithm is powered up, it initializes its routing-protocol data structures and then waits for indications from lower-layer protocols that its interfaces are functional. After a router is assured that its interfaces are functioning, it uses the OSPF Hello protocol to acquire neighbors, which are routers with interfaces to a common network. The router sends hello packets to its neighbors and receives their hello packets. In addition to helping acquire neighbors, hello packets also act as “keepalives,” messages that let routers know that other routers are still functional. On multi-access networks (networks supporting more than two routers), the Hello protocol elects a designated router and a backup designated router. Among other things, the designated router is responsible for generating LSAs for the entire multi-access network. Designated routers allow a reduction in network traffic and in the size of the topological database.
When the topological databases of two neighboring routers are synchronized, the routers are said to be adjacent. Adjacencies control the distribution of routing-protocol packets, which are sent and received only on adjacencies. Each router periodically sends its LSAs to provide information on a router's adjacencies or to inform others when a router's state changes. By comparing established adjacencies to link states, failed routers can be detected quickly, and the network's topology can be altered appropriately. From the topological database generated from LSAs, each router calculates a shortest-path tree (SPT), with itself as root. The SPT, in turn, yields a routing table.
In Mobile Ad-hoc Networks (MANET), there are highly-meshed connections. Due to prohibitive overhead costs of maintaining many peerings, it is not always desirable to bring up routing peering with all possible visible neighbors. But this results in lost, potentially-usable forwarding paths. There is a need for a solution that does not have to perform a full database exchange, but at the same time assumes the adjacency is synchronized and announces the corresponding link for transit. This would reduce peering overhead, and the many alternate paths could be used, thus more effectively utilizing available network throughput. In the case of OSPF, the use of many alternate paths translates into the ability to announce and use the adjacency (for data plane) without incurring the expense of a full database exchange or handling flooding updates over this adjacency.
In OSPF, before two nodes can announce an adjacency to each other and use their common link for forwarding data, they have to exchange their databases through database description (DD) packets to assure that their databases are synchronized. In situations where nodes already have a synchronized database and establish a new adjacency over a link, they spend some time in exchanging their database even though their database might be already synchronized. This is a time-consuming process that also requires processing resources on two separate routers. As processing resources can be better used for other tasks, there is a heartfelt need to reduce the amount of database exchange to free up processing resources and simplify communication between routers in a network.